package com.tucc.hello.leetcode.no1_400.no1_200.no61_80.no68;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        String[] words = {"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"};
        String[] words = {"What", "must", "be", "acknowledgment", "shall", "be"};

        List<String> result = solution.fullJustify(words, 16);

        for (String string : result) {
            System.out.println("|" + string + "|");
        }
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int curLen = 0;
        int curStart = 0;
        for (int i = 0; i < words.length; i++) {
            int nextLen = curLen + words[i].length();
            if (nextLen + (i - curStart) > maxWidth) {
                addLine(i - 1, curStart, maxWidth, curLen, words, result);
                curStart = i;
                curLen = words[i].length();
            } else {
                curLen += words[i].length();
            }
        }
//        addLine(words.length - 1, curStart, maxWidth, curLen, words, result);
        StringBuilder lineBuilder = new StringBuilder(words[curStart]);
        for (int i = curStart + 1; i < words.length; i++) {
            lineBuilder.append(" ").append(words[i]);
        }
        while (lineBuilder.length() < maxWidth) {
            lineBuilder.append(" ");
        }
        result.add(lineBuilder.toString());
        return result;
    }

    public void addLine(int i, int curStart, int maxWidth, int curLen, String[] words,
                        List<String> result) {
        int spaceNum = (maxWidth - curLen);
        int wordNum = (i - curStart) + 1;
        int baseSpace = wordNum == 1 ? spaceNum : spaceNum / (wordNum - 1);
        StringBuilder spaceTemplate = new StringBuilder();
        for (int j = 0; j < baseSpace; j++) {
            spaceTemplate.append(" ");
        }
        int additionSpace = wordNum == 1 ? 0 : spaceNum - (wordNum - 1) * baseSpace;
        StringBuilder additionSpaceTemplate = new StringBuilder(spaceTemplate)
                .append(" ");
        StringBuilder lineBuilder = new StringBuilder();
        lineBuilder.append(words[curStart]);
        for (int j = 1; j < wordNum; j++) {
            if (j <= additionSpace) {
                lineBuilder.append(additionSpaceTemplate);
            } else {
                lineBuilder.append(spaceTemplate);
            }
            lineBuilder.append(words[curStart + j]);
        }
        if (wordNum == 1) {
            lineBuilder.append(spaceTemplate);
        }
        result.add(lineBuilder.toString());
    }
}
